package hot100.logos21To30;

import hot100.datastruct.ListNode;

/**
 * @author logos
 * date 2025/7/12 11:51
 * @version v1.0
 * @Package hot100
 */
public class logos24 {

    /**
     * 24.回文链表
     * https://leetcode.cn/problems/palindrome-linked-list/?envType=study-plan-v2&envId=top-100-liked
     */

    public boolean isPalindrome(ListNode head) {
        ListNode mid = getMidNode(head);
        ListNode lastNode = reverse(mid);
        boolean ans = true;
        ListNode left = head;
        ListNode right = lastNode;
        while (right != null) {
            if (left.val != right.val) {
                ans = false;
            }
            left = left.next;
            right = right.next;
        }
        reverse(lastNode);
        left = head;
        while (left != null) {
            System.out.print(left.val + " ");
            left = left.next;
        }
        return ans;
    }

    private ListNode getMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode tmp = head;
        ListNode next = null;
        while (tmp != null) {
            next = tmp.next;
            tmp.next = pre;
            pre = tmp;
            tmp = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        logos24 solution = new logos24();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2,node1);
        ListNode node3 = new ListNode(3,node2);
        ListNode node4 = new ListNode(4,node3);
        ListNode node5 = new ListNode(5,node4);
        ListNode node6 = new ListNode(4,node5);
        ListNode node7 = new ListNode(3,node6);
        ListNode node8 = new ListNode(2,node7);
        ListNode node9 = new ListNode(1,node8);
        System.out.println(solution.isPalindrome(node9));
        System.out.println(solution.isPalindrome(node8));
    }
}
